Matemática Discreta: Anatomia de uma Rede de Transporte

Uma rede de transporte é uma estrutura matemática especializada usada para modelar o movimento de bens, dados ou materiais através de um sistema de condutos restritos. Ela transforma um grafo direcionado padrão em um quadro funcional ao designar pontos específicos de origem e destino, enquanto impõe limites físicos de "boca de buraco" em cada conexão dentro do sistema.

A Definição de uma Rede de Transporte

De acordo com Definição 10.1.1, uma rede de transporte (ou simplesmente uma rede) é um grafo simples, ponderado e direcionado que deve satisfazer três critérios fundamentais:

Propriedade (a): A Fonte

Um vértice designado, a fonte ($a$ ou $s$), representa o ponto de origem. Não possui arestas entrantes (grau de entrada = 0) e atua como um fornecedor infinito.

Propriedade (b): O Ponto Final

Um vértice designado, a ponto final ($z$ ou $t$), representa o consumidor final. Não possui arestas saindo dele (grau de saída = 0).

Propriedade (c): Capacidade

O peso $C_{ij}$ de cada aresta direcionada $(i, j)$ é chamado sua capacidade. Isso deve ser um número não negativo ($C_{ij} \geq 0$), representando o fluxo máximo possível que a aresta pode suportar.

Analogia do Mundo Real: A Rede Elétrica Regional

Para tornar esses conceitos abstratos mais tangíveis, considere uma rede elétrica regional:

A Fonte: Uma grande represa hidrelétrica. Ela produz apenas energia; nenhuma eletricidade entra na represa a partir da própria rede.
O Ponto Final: Uma zona industrial pesada. Ela consome toda a eletricidade que entra para alimentar suas máquinas; nada é devolvido à rede.
Arestas e Capacidades: As linhas de transmissão são as arestas. Sua capacidade é a corrente máxima que os fios físicos podem suportar antes de falhar por superaquecimento.
Vértices Intermediários: Subestações locais que redirecionam o fluxo sem "consumir" o material (Conservação de Fluxo).

Nuances entre Capacidade e Fluxo

É fundamental distinguir entre Capacidade e Fluxo. A capacidade $C_{ij}$ é uma propriedade física estática — é o volume potencial. O fluxo $F_{ij}$ é o volume real sendo movido em um momento específico. Neste slide, focamos exclusivamente nos limites arquitetônicos (capacidades) e não no estado atual do movimento.

🎯 Princípio Central: Restrições Estruturais

Toda rede de transporte é um grafo direcionado onde o fluxo se move de um fornecedor (Fonte) para um consumidor (Ponto Final) através de condutos limitados por capacidades não negativas.

Fonte: $deg^-(a) = 0 \quad | \quad$ Ponto Final: $deg^+(z) = 0 \quad | \quad \text{Capacidade}: C_{ij} \geq 0

PERGUNTA 1

Quais são os três componentes obrigatórios de uma rede de transporte de acordo com a Definição 10.1.1?

Grafo direcionado, fonte/ponto final únicos e capacidades não negativas.

Grafo não direcionado, fontes infinitas e pesos negativos.

Grafo ponderado, emparelhamento bipartido e graus de entrada iguais.

Grafo simples, fonte com grau de entrada 1 e arestas com capacidade zero.

PERGUNTA 2

Qual é a diferença principal entre Capacidade ($C_{ij}$) e Fluxo ($F_{ij}$)?

A capacidade é o limite máximo; o fluxo é a quantidade real que está se movimentando atualmente.

A capacidade é dinâmica; o fluxo é uma propriedade física estática.

A capacidade aplica-se apenas ao ponto final; o fluxo aplica-se apenas à fonte.

Não há diferença; são termos intercambiáveis na teoria de redes.

PERGUNTA 3

No contexto de um modelo de rede elétrica, qual seria a representação da Fonte?

Uma usina geradora de energia como uma represa hidrelétrica.

Um bairro residencial consumindo eletricidade.

Uma subestação intermediária redirecionando energia.

Os fios físicos de cobre usados para transmissão.

PERGUNTA 4

Enuncie a condição para que um vértice $z$ seja considerado um Ponto Final.

Ele deve ter um grau de saída igual a zero ($deg^+(z) = 0$).

Ele deve ter um grau de entrada igual a zero ($deg^-(z) = 0$).

A soma de suas capacidades deve ser infinita.

Ele deve estar conectado a todos os outros nós no grafo.

PERGUNTA 5

[🧩 SYSTEM_FORCED] O que é uma rede? (Foco nos critérios da Definição 10.1.1).

Um grafo simples, ponderado e direcionado com uma fonte designada (sem arestas entrantes), um ponto final designado (sem arestas saindo) e capacidades não negativas em todas as arestas.

Um grafo bipartido onde cada nó tem uma aresta correspondente.

Qualquer grafo que contenha um caminho do nó a ao nó z.

Um grafo direcionado onde o número de arestas é igual ao número de vértices.